Foundations of Query Languages

Organizers:

Tutor:

Course Contents:

The lecture covers a variety of topics on the foundations of database query languages, discussing classical as well as recent developments in database research. It will be split into two main parts.

In the first part we will discuss several query optimization approaches, i.e. given a database query that we want to evaluate on a database, we will get to know methods which allow us to process the query more efficiently than traditional methods. One branch of research that we will discuss here is rewriting the query into a more efficient but equivalent form, i.e. removing redundant operations.
In the second part we will come to issues of expressiveness of query languages. As a simple example, we will see that there is no relational algebra query that computes the transitive closure of a graph. This is due to the fact that we have no operator in relational algebra that expresses some kind of loop. On the one hand we will see query languages that add recursion to the algebra and therefore are more expressive (i.e. this means that we are able to compute the transitive closure of a graph with them). On the other hand this comes at the price of a provably higher cost of query evaluation. We will discuss the effect of adding different operators to a query language (like minus, union, intersection, recursion) on query evaluation cost.

At the end of this course the students have the necessary background to understand recent research papers.

Link to the module description (in German)

Necessary Prerequisites:

The key course (Kursvorlesung) 'Databases and Information Systems'.

Time, Location and Organization:

Lecture: Mo 2pm - 4pm, Building 101, Room 01-018
Tutorials: Wed 9am - 11am, Bulding 51, Room 00-034
Language: English
ECTS: 6 Points
Program of Study:: Master CS, Applied CS, Lehramt
Exam: There will be a written exam at the end of the term. Its date is to be announced.

Exercises

Tutorials will take place on Wednesday. Every exercise sheet is published on Wednesday and your solution to it is to be handed in the next Wednesday before the exercise class begins. The due date is written on the sheet. As prerequisites to take the final exam you have to

work on at least 50 percent of the exercises on every sheet in a constructive way (with exception of at most one sheet),
be present in the tutorials (with exception of at most one tutorial session),
hand in your own solutions or in a group of at most two people, (i.e. copying from other students is not allowed).

Literature:

Additional reading material will be announced on the lecture slides.